package com.mgq.algorithm.link;

/**
 * @author MaGuangQi
 * 返回单链表的倒数第k个元素
 * @date 2021-12-31 14:02
 **/
public class LinkedListKNode {
    /**
     * 思路:
     * 首先让p1先走k步,然后p2指向头,这时候p1和p2一直相差k
     * 最后让p1走向最后的null时,这时候p2其实指向的位置就是倒数第k个元素
     *
     * @param head
     * @param k
     * @return
     */
    public ListNode findFromEnd(ListNode head,int k) {
        if (head==null) return null;
        ListNode p1=head;
        ListNode p2=head;
        //p1先走k步
        for (int i = 0; i < k; i++) {
            p1=p1.next;
        }
        // p1 和 p2 同时走 n - k 步
        while (p1 != null) {
            p2=p2.next;
            p1=p1.next;
        }
        //最终p2就是倒数第k个元素
        return p2;
    }
}
